#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

int staircase2(int height) {
  if (height == 0 || height == 1) {
    return 1;
  }

  return staircase2(height - 1) + staircase2(height - 2);
}

int staircase3(int height) {
  if (height == 0 || height == 1) {
    return 1;
  }
  else if (height == 2) {
    return 2;
  }

  return staircase3(height - 1) + staircase3(height - 2) + staircase3(height - 3);
}

int ways(int max_step, int height) {
  if (height == 0 || height == 1) {
    return 1;
  }

  int steps = 0;

  for (int i = 1; i <= min(height, max_step); ++i) {
    steps += ways(max_step, height - i);
  }

  return steps;
}

int ways_dp(int max_step, int height) {
  if (height < 2) {
		return 1;
	}
  
  vector<int> steps(height + 1, 0);
  steps[0] = 1;
  steps[1] = 1;

  for (int curr_height = 2; curr_height <= height; ++curr_height) {
    // steps[curr_height] = 
    //   steps[curr_height - 1] + 
    //   steps[curr_height - 2] + 
    //   ... + 
    //   steps[curr_height - min(max_step, height)]

    int j = 1;
    while (j <= curr_height && j <= max_step) {
      steps[curr_height] += steps[curr_height - j];
      ++j;
    }
  }

  return steps.back();
}

int main(int argc, char const *argv[])
{
  /* code */
  cout << ways_dp(2, 5) << endl;
  return 0;
}
